Spanning Forest

定义 Definition

（图论/算法）生成森林：在一个（可能不连通的）图中，选取若干条边，使得每个连通分量都被一棵生成树“覆盖”，整体形成一个森林；它包含所有顶点、无环，且在每个连通分量内保持连通。常见变体有 minimum spanning forest（最小生成森林）。

发音 Pronunciation (IPA)

/ˈspænɪŋ ˈfɔːrɪst/

例句 Examples

A spanning forest has no cycles and includes all vertices.
生成森林没有环，并且包含所有顶点。

When the graph is disconnected, Kruskal’s algorithm produces a minimum spanning forest by finding a minimum spanning tree in each component.
当图是不连通的时，Kruskal 算法会通过在每个连通分量中找到最小生成树，从而得到最小生成森林。

词源 Etymology

spanning 来自动词 span（“跨越、覆盖”），表示“覆盖到所有顶点/范围”；forest 在图论中借用日常“森林”的比喻，指由多棵不相连的“树（tree）”组成的结构。因此 spanning forest 字面意思就是“覆盖全体（顶点）的森林”。

相关词 Related Words

• Graph
• Vertex
• Edge
• Tree
• Forest
• Spanning Tree
• Minimum Spanning Tree
• Kruskal
• Prim
• Connected Component

文献与作品 Literary / Notable Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）——在最小生成树与不连通图的讨论中涉及生成森林/最小生成森林。
• Graph Theory（Bondy & Murty）——以“树、森林、生成子图”等概念体系中出现。
• The Design and Analysis of Computer Algorithms（Aho, Hopcroft, Ullman）——在经典图算法（如 Kruskal/Prim）背景下使用相关术语。